SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Intersection graph</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Intersection graph</span></span>

</h1>

</header>

<p>In <a href="Graph_theory" title="Graph theory">graph theory</a>, an <b>intersection graph</b> is a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> that represents the pattern of <a href="Intersection_(set_theory)" title="Intersection (set theory)">intersections</a> of a family of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a>. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

<p>Formally, an intersection graph <span class="texhtml mvar" style="font-style:italic;">G</span> is an <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a> formed from a family of sets

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i},\,\,\,i=0,1,2,\dots }</annotation>

</semantics>

</math></span><img src="./bc83c8365151b45d84e5ff666b12b1fded62a59f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.633ex; height:2.509ex;" alt="{\displaystyle S_{i},\,\,\,i=0,1,2,\dots }" loading="lazy"></span></dd></dl>

<p>by creating one vertex <span class="texhtml mvar" style="font-style:italic;">v<sub>i</sub></span> for each set <span class="texhtml mvar" style="font-style:italic;">S<sub>i</sub></span>, and connecting two vertices <span class="texhtml mvar" style="font-style:italic;">v<sub>i</sub></span> and <span class="texhtml mvar" style="font-style:italic;">v<sub>j</sub></span> by an edge whenever the corresponding two sets have a <a href="Empty_set" title="Empty set">nonempty</a> intersection, that is,

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.}</annotation>

</semantics>

</math></span><img src="./15368096b7e98d1c8dced53d0980b14888f953b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:38.038ex; height:3.009ex;" alt="{\displaystyle E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="All_graphs_are_intersection_graphs">All graphs are intersection graphs</h2></div>

<p>Any undirected graph <span class="texhtml mvar" style="font-style:italic;">G</span> may be represented as an intersection graph. For each vertex <span class="texhtml mvar" style="font-style:italic;">v<sub>i</sub></span> of <span class="texhtml mvar" style="font-style:italic;">G</span>, form a set <span class="texhtml mvar" style="font-style:italic;">S<sub>i</sub></span> consisting of the edges incident to <span class="texhtml mvar" style="font-style:italic;">v<sub>i</sub></span>; then two such sets have a nonempty intersection <a href="If_and_only_if" title="If and only if">if and only if</a> the corresponding vertices share an edge. Therefore, <span class="texhtml mvar" style="font-style:italic;">G</span> is the intersection graph of the sets <span class="texhtml mvar" style="font-style:italic;">S<sub>i</sub></span>.

</p><p><a href="#CITEREFErdősGoodmanPósa1966">Erdős, Goodman & Pósa (1966)</a> provide a construction that is more efficient, in the sense that it requires a smaller total number of elements in all of the sets <span class="texhtml mvar" style="font-style:italic;">S<sub>i</sub></span> combined. For it, the total number of set elements is at most <span class="texhtml"><style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style><span class="sfrac">⁠<span class="tion"><span class="num"><i>n</i><sup>2</sup></span><span class="sr-only">/</span><span class="den">4</span></span>⁠</span></span>, where <span class="texhtml mvar" style="font-style:italic;">n</span> is the number of vertices in the graph. They credit the observation that all graphs are intersection graphs to <a href="#CITEREFSzpilrajn-Marczewski1945">Szpilrajn-Marczewski (1945)</a>, but say to see also <a href="#CITEREFČulík1964">Čulík (1964)</a>. The <a href="Intersection_number_(graph_theory)" title="Intersection number (graph theory)">intersection number</a> of a graph is the minimum total number of elements in any intersection representation of the graph.

</p>

<div class="mw-heading mw-heading2"><h2 id="Classes_of_intersection_graphs">Classes of intersection graphs</h2></div>

<p>Many important graph families can be described as intersection graphs of more restricted types of set families, for instance sets derived from some kind of geometric configuration:

</p>

<ul><li>An <a href="Interval_graph" title="Interval graph">interval graph</a> is defined as the intersection graph of intervals on the real line, or of connected subgraphs of a <a href="Path_graph" title="Path graph">path graph</a>.</li>

<li>An <a href="Indifference_graph" title="Indifference graph">indifference graph</a> may be defined as the intersection graph of unit intervals on the real line</li>

<li>A <a href="Circular_arc_graph" class="mw-redirect" title="Circular arc graph">circular arc graph</a> is defined as the intersection graph of <a href="Circular_arc" title="Circular arc">arcs on a circle</a>.</li>

<li>A <a href="Polygon-circle_graph" title="Polygon-circle graph">polygon-circle graph</a> is defined as the intersection of polygons with corners on a circle.</li>

<li>One characterization of a <a href="Chordal_graph" title="Chordal graph">chordal graph</a> is as the intersection graph of connected subgraphs of a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>.</li>

<li>A <a href="Trapezoid_graph" title="Trapezoid graph">trapezoid graph</a> is defined as the intersection graph of trapezoids formed from two parallel lines. They are a generalization of the notion of <a href="Permutation_graph" title="Permutation graph">permutation graph</a>, in turn they are a special case of the family of the complements of <a href="Comparability_graph" title="Comparability graph">comparability graphs</a> known as cocomparability graphs.</li>

<li>A <a href="Unit_disk_graph" title="Unit disk graph">unit disk graph</a> is defined as the intersection graph of <a href="Unit_disk" title="Unit disk">unit disks</a> in the plane.</li>

<li>A <a href="Circle_graph" title="Circle graph">circle graph</a> is the intersection graph of a set of chords of a circle.</li>

<li>The <a href="Circle_packing_theorem" title="Circle packing theorem">circle packing theorem</a> states that <a href="Planar_graph" title="Planar graph">planar graphs</a> are exactly the intersection graphs of families of closed disks in the plane bounded by non-crossing circles.</li>

<li><a href="Scheinerman's_conjecture" title="Scheinerman's conjecture">Scheinerman's conjecture</a> (now a theorem) states that every planar graph can also be represented as an intersection graph of <a href="Line_segment" title="Line segment">line segments</a> in the plane. However, intersection graphs of line segments may be nonplanar as well, and recognizing intersection graphs of line segments is <a href="Complete_(complexity)" title="Complete (complexity)">complete</a> for the <a href="Existential_theory_of_the_reals" title="Existential theory of the reals">existential theory of the reals</a> (<a href="#CITEREFSchaefer2010">Schaefer 2010</a>).</li>

<li>The <a href="Line_graph" title="Line graph">line graph</a> of a graph <i>G</i> is defined as the intersection graph of the edges of <i>G</i>, where we represent each edge as the set of its two endpoints.</li>

<li>A <a href="String_graph" title="String graph">string graph</a> is the intersection graph of <a href="Plane_curve" title="Plane curve">curves on a plane</a>.</li>

<li>A graph has <a href="Boxicity" title="Boxicity">boxicity</a> <i>k</i> if it is the intersection graph of multidimensional <a href="Hyperrectangle" title="Hyperrectangle">boxes</a> of dimension <i>k</i>, but not of any smaller dimension.</li>

<li>A <a href="Clique_graph" title="Clique graph">clique graph</a> is the intersection graph of <a href="Maximal_clique" class="mw-redirect" title="Maximal clique">maximal cliques</a> of another graph</li>

<li>A <a href="Block_graph" title="Block graph">block graph</a> of clique tree is the intersection graph of <a href="Biconnected_component" title="Biconnected component">biconnected components</a> of another graph</li></ul>

<p><a href="#CITEREFScheinerman1985">Scheinerman (1985)</a> characterized the <b>intersection classes of graphs</b>, families of finite graphs that can be described as the intersection graphs of sets drawn from a given family of sets. It is necessary and sufficient that the family have the following properties:

</p>

<ul><li>Every <a href="Induced_subgraph" title="Induced subgraph">induced subgraph</a> of a graph in the family must also be in the family.</li>

<li>Every graph formed from a graph in the family by replacing a vertex by a <a href="Clique_(graph_theory)" title="Clique (graph theory)">clique</a> must also belong to the family.</li>

<li>There exists an infinite sequence of graphs in the family, each of which is an induced subgraph of the next graph in the sequence, with the property that every graph in the family is an induced subgraph of a graph in the sequence.</li></ul>

<p>If the intersection graph representations have the additional requirement that different vertices must be represented by different sets, then the clique expansion property can be omitted.

</p>

<div class="mw-heading mw-heading2"><h2 id="Related_concepts">Related concepts</h2></div>

<p>An <a href="Order_theory" title="Order theory">order-theoretic</a> analog to the intersection graphs are the <a href="Inclusion_order" title="Inclusion order">inclusion orders</a>. In the same way that an intersection representation of a graph labels every vertex with a set so that vertices are adjacent if and only if their sets have nonempty intersection, so an inclusion representation <i>f</i> of a <a href="Poset" class="mw-redirect" title="Poset">poset</a> labels every element with a set so that for any <i>x</i> and <i>y</i> in the poset, <i>x</i> ≤ <i>y</i> if and only if <i>f</i>(<i>x</i>) ⊆ <i>f</i>(<i>y</i>).

</p>

<ul><li><a href="Contact_graph" title="Contact graph">Contact graph</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFČulík1964" class="citation cs2">Čulík, K. (1964), "Applications of graph theory to mathematical logic and linguistics", <i>Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963)</i>, Prague: Publ. House Czechoslovak Acad. Sci., pp. <span class="nowrap">13–</span>20, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0176940">0176940</a></cite>.</li>

<li><cite id="CITEREFErdősGoodmanPósa1966" class="citation cs2"><a href="Paul_Erd%C5%91s" title="Paul Erdős">Erdős, Paul</a>; Goodman, A. W.; <a href="Lajos_P%C3%B3sa_(mathematician)" title="Lajos Pósa (mathematician)">Pósa, Louis</a> (1966), <a rel="nofollow" class="external text" href="http://www.renyi.hu/~p_erdos/1966-21.pdf">"The representation of a graph by set intersections"</a> <span class="cs1-format">(PDF)</span>, <i>Canadian Journal of Mathematics</i>, <b>18</b> (1): <span class="nowrap">106–</span>112, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1966-014-3">10.4153/CJM-1966-014-3</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0186575">0186575</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:646660">646660</a></cite>.</li>

<li><cite id="CITEREFGolumbic1980" class="citation cs2"><a href="Martin_Charles_Golumbic" title="Martin Charles Golumbic">Golumbic, Martin Charles</a> (1980), <i>Algorithmic Graph Theory and Perfect Graphs</i>, Academic Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-289260-7</bdi></cite>.</li>

<li><cite id="CITEREFMcKeeMcMorris1999" class="citation cs2">McKee, Terry A.; McMorris, F. R. (1999), <i>Topics in Intersection Graph Theory</i>, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89871-430-3</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1672910">1672910</a></cite>.</li>

<li><cite id="CITEREFSzpilrajn-Marczewski1945" class="citation cs2"><a href="Edward_Marczewski" title="Edward Marczewski">Szpilrajn-Marczewski, E.</a> (1945), "Sur deux propriétés des classes d'ensembles", <i>Fund. Math.</i>, <b>33</b>: <span class="nowrap">303–</span>307, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Ffm-33-1-303-307">10.4064/fm-33-1-303-307</a></span>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0015448">0015448</a></cite>.</li>

<li><cite id="CITEREFSchaefer2010" class="citation cs2">Schaefer, Marcus (2010), <a rel="nofollow" class="external text" href="http://ovid.cs.depaul.edu/documents/convex.pdf">"Complexity of some geometric and topological problems"</a> <span class="cs1-format">(PDF)</span>, <i><a href="International_Symposium_on_Graph_Drawing" title="International Symposium on Graph Drawing">Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers</a></i>, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. <span class="nowrap">334–</span>344, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-11805-0_32">10.1007/978-3-642-11805-0_32</a></span>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-11804-3</bdi></cite>.</li>

<li><cite id="CITEREFScheinerman1985" class="citation cs2">Scheinerman, Edward R. (1985), "Characterizing intersection classes of graphs", <i>Discrete Mathematics</i>, <b>55</b> (2): <span class="nowrap">185–</span>193, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2885%2990047-0">10.1016/0012-365X(85)90047-0</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0798535">0798535</a></cite>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li>For an overview of both the theory of intersection graphs and important special classes of intersection graphs, see <a href="#CITEREFMcKeeMcMorris1999">McKee & McMorris (1999)</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Jan Kratochvíl, <a rel="nofollow" class="external text" href="http://videolectures.net/sicgt07_kratochvil_gig/">A video lecture on intersection graphs (June 2007)</a></li>

<li>E. Prisner, <a rel="nofollow" class="external text" href="http://www.eprisner.de/Journey/Rahmen.html">A Journey through Intersection Graph County</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-02-09" href="https://en.wikipedia.org/wiki/?title=Intersection_graph&oldid=1205563104">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>